package de.tu_darmstadt.gdi1.xcom.controller.ai;

import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;

import de.tu_darmstadt.gdi1.framework.utils.Point;
import de.tu_darmstadt.gdi1.xcom.controller.ai.GameGridNode.cellStatus;
import de.tu_darmstadt.gdi1.xcom.controller.events.ActionEnum;
import de.tu_darmstadt.gdi1.xcom.model.XcomGameConstants;
import de.tu_darmstadt.gdi1.xcom.model.elements.DirectionEnum;
import de.tu_darmstadt.gdi1.xcom.model.elements.GameElement;
import de.tu_darmstadt.gdi1.xcom.model.elements.Monster;

/**
 * Unfortunately, Java doesn't allow functions inside of functions.
 * To keep the code clean, I put all this in its own class.
 * Just pretend that all functions are inside findPath()
 * 
 * @author michael
 *
 */

public class PathFinder {

	Random rand = new Random();
	
	XcomAIGame game;
	Point start;
	DirectionEnum initialMonsterDirection;
	Point goal;
	
	GameGridNode[][] map;
	// points next to those that are already vetted
	ArrayList<Point> border = new ArrayList<Point>();
	
	
	public Stack<ActionEnum> findPath(XcomAIGame g, Point startPoint, Point destination) {
		
		
		game = g;
		start = startPoint;
		goal = destination;
		
		// DEBUG:	Try definitely possible path instead
		//start = new Point(3,1);
		//goal = new Point(4,1);
		
		System.out.println("PathFinder: from "+start+" to "+goal);
		
		// if locked in: do nothing
		// might crash if at the edge of the map, but the map
		// should be surrounded by walls anyways
		if(
				   game.blockedForAI(Point.modifyXAxis(start, +1))
				&& game.blockedForAI(Point.modifyXAxis(start, -1))
				&& game.blockedForAI(Point.modifyYAxis(start, +1))
				&& game.blockedForAI(Point.modifyYAxis(start, -1))
		) {
			System.out.println("Pathfinder: Locked in! Can't move!");
			return null;
		}
		
		// not locked in? pick a location that has room for a mob
		// (this crashes if the map is full, but there should never
		// be a full map)
		//Point goal;
		//do {
		//	goal = new Point(rand.nextInt(game.getMapWidth()),rand.nextInt(game.getMapHeight()));
		//} while (game.getElementsAt(goal).get(0).isSolid());
		
		
		
		//System.out.println("PathFinder: Found empty goal field");
		
		// initialize map abstraction
		map = new GameGridNode[game.getMapWidth()][game.getMapHeight()];
		
		for(int iHateJava = 0; iHateJava < map.length; iHateJava++)
			for(int jAvaSucks = 0; jAvaSucks < map[0].length ; jAvaSucks++) {
				// horrible code ahead!
				map[iHateJava][jAvaSucks] = new GameGridNode(new Point(iHateJava,jAvaSucks), null, Integer.MAX_VALUE, game.blockedForAI(new Point(iHateJava,jAvaSucks)) ? cellStatus.BLOCKED : cellStatus.FAR );
			}
		
		// Distance to where I am is known already
		map[start.getX()][start.getY()].pathCost = 0;
		
		// initial border are traversable places next to start position
		
		// neighbours of starting point
		Point pointNorth = Point.modifyYAxis(start, -1);
		Point pointEast  = Point.modifyXAxis(start, +1);
		Point pointSouth = Point.modifyYAxis(start, +1);
		Point pointWest  = Point.modifyXAxis(start, -1);
		
		// adjust point of origin
		map[pointNorth.getX()][pointNorth.getY()].pointOrigin = start;
		map[pointNorth.getX()][pointNorth.getY()].pathCost = XcomGameConstants.COST_WALK;
		map[pointSouth.getX()][pointSouth.getY()].pointOrigin = start;
		map[pointSouth.getX()][pointSouth.getY()].pathCost = XcomGameConstants.COST_WALK;
		map[pointEast. getX()][pointEast.getY() ].pointOrigin = start;
		map[pointEast.getX() ][pointEast.getY() ].pathCost = XcomGameConstants.COST_WALK;
		map[pointWest.getX() ][pointWest.getY() ].pointOrigin = start;
		map[pointWest.getX() ][pointWest.getY() ].pathCost = XcomGameConstants.COST_WALK;
		
		// out of these candidates, the vacant ones
		// are the initial border
		if(map[pointNorth.getX()][pointNorth.getY()].status != cellStatus.BLOCKED) {
			border.add(pointNorth);
			map[pointNorth.getX()][pointNorth.getY()].status = cellStatus.BORDER;
		}
		if(map[pointSouth.getX()][pointSouth.getY()].status != cellStatus.BLOCKED) {
			border.add(pointSouth);
			map[pointSouth.getX()][pointSouth.getY()].status = cellStatus.BORDER;
		}
		if(map[pointEast.getX() ][pointEast.getY() ].status != cellStatus.BLOCKED) {
			border.add(pointEast);
			map[pointEast.getX()][pointEast.getY()].status = cellStatus.BORDER;
		}
		if(map[pointWest.getX() ][pointWest.getY() ].status != cellStatus.BLOCKED) {
			border.add(pointWest);
			map[pointWest.getX()][pointWest.getY()].status = cellStatus.BORDER;
		}
		
		System.out.println("PathFinder: Border has "+border.size());
		
		// initialization complete. Begin path finding.
		
		boolean foundPath = false;
		
		while(!border.isEmpty()) {
			// pick most promising border node
			Point pcandidate = getBestBorderNode();
			GameGridNode nc = map[pcandidate.getX()][pcandidate.getY()];
			
			// push the border
			border.remove(pcandidate);
			nc.status = cellStatus.CHECKED;
			
			// have we reached the goal yet?
			// If so, stop. If not, expand border
			if(pcandidate.equals(goal)) {
				foundPath = true;
				break;
			}
			
			// Not done yet? check out neighbours
			Point pn = Point.modifyYAxis(pcandidate, +1);
			Point ps = Point.modifyYAxis(pcandidate, -1);
			Point pe = Point.modifyXAxis(pcandidate, +1);
			Point pw = Point.modifyXAxis(pcandidate, -1);
			
			// add the vacant ones to border, if they aren't already.
			GameGridNode nn = map[pn.getX()][pn.getY()];
			GameGridNode ns = map[ps.getX()][ps.getY()];
			GameGridNode ne = map[pe.getX()][pe.getY()];
			GameGridNode nw = map[pw.getX()][pw.getY()];
			if(nn.status == cellStatus.FAR) {
				nn.status = cellStatus.BORDER;
				nn.pointOrigin = pcandidate;
				nn.pathCost = nc.pathCost + XcomGameConstants.COST_WALK;
				border.add(pn);
			}
			if(ns.status == cellStatus.FAR) {
				ns.pointOrigin = pcandidate;
				ns.pathCost = nc.pathCost + XcomGameConstants.COST_WALK;
				ns.status = cellStatus.BORDER;
				border.add(ps);
			}
			if(ne.status == cellStatus.FAR) {
				ne.pointOrigin = pcandidate;
				ne.pathCost = nc.pathCost + XcomGameConstants.COST_WALK;
				ne.status = cellStatus.BORDER;
				border.add(pe);
			}
			if(nw.status == cellStatus.FAR) {
				nw.pointOrigin = pcandidate;
				nw.pathCost = nc.pathCost + XcomGameConstants.COST_WALK;
				nw.status = cellStatus.BORDER;
				border.add(pw);
			}
			
			
		}
		
		if(foundPath)
			return formulatePlan();
		else {
			System.out.println("PathFinder: Could not find path!");
			return null; // :(
		}
	}
	
	Point getBestBorderNode() {
		if(border.isEmpty()) {
			System.out.println("PathFinder: Border is empty!");
			return null;
		}
		
		// pick most promising border cell
		
		// pick first one
		Point bestPoint = border.get(0);
		// approximate distance
		int bestDistance = 
			manhattanDistance(bestPoint,goal)
			+map[bestPoint.getX()][bestPoint.getY()].pathCost; // FIXME
		
		// check if there's one that has a better distance
		for(Point p : border) {
			// find the one with the shortest estimated distance
			int estimate = map[p.getX()][p.getY()].pathCost + manhattanDistance(p,goal);
			if(estimate < bestDistance) {
				bestPoint = p;
				bestDistance = estimate;
			}
		}
		
		System.out.println("Best point: "+bestPoint);
		
		return bestPoint;
	
	}
	
	/**
	 * Only call this, when an actual path has been found!
	 * @return stack of actions to be taken to reach the destination
	 */
	Stack<ActionEnum> formulatePlan() {
		Stack<ActionEnum> plan = new Stack<ActionEnum>();
		
		// please note that all this code works
		// in reverse direction!
		Point focus = goal;
		Point before;
		DirectionEnum nextDir = null; // direction "after" reaching the goal
		DirectionEnum dirHere;
		do {
			before = map[focus.getX()][focus.getY()].pointOrigin;
			dirHere = directionFromTo(before,focus);
			
			// requires a turn? Insert a turn!
			// FIX: Monsters don't turn
			
			if(nextDir != null)
				if(nextDir != dirHere) {
					switch(directionDiff(dirHere,nextDir)) {
					case -2: 
						plan.push(ActionEnum.RotateLeft);
						plan.push(ActionEnum.RotateLeft);
						break;
					case -1:
						plan.push(ActionEnum.RotateLeft);
						break;
					case 0:
						// impossible case!
						System.err.println("Unreachable code in Pathfinder.formulatePlan!");
						break;
					case 1:
						plan.push(ActionEnum.RotateRight);
						break;
					}
					
				}
			
			// walk here
			plan.push(ActionEnum.Move);
			
			nextDir = dirHere;
			focus = before;
					
		} while(before != start);
		
		// add initial rotations
		
		// pick Monster
		for(GameElement ge :  game.getElementsAt(start)) {
			if(ge.getClass().equals(Monster.class)) {
				initialMonsterDirection = ((Monster)ge).getDirection();
				break;
			}
		}
		
		switch(directionDiff(initialMonsterDirection,nextDir)) {
		case -2: 
			plan.push(ActionEnum.RotateLeft);
			plan.push(ActionEnum.RotateLeft);
			break;
		case -1:
			plan.push(ActionEnum.RotateLeft);
			break;
		case 0:
			// already facing right direction
			break;
		case 1:
			plan.push(ActionEnum.RotateRight);
			break;
		}
		
		// plan complete!
		
		return plan;
	}
	
	DirectionEnum directionFromTo(Point from, Point to) {
		if(from.getX() < to.getX()) return DirectionEnum.East;
		if(from.getX() > to.getX()) return DirectionEnum.West;
		if(from.getY() < to.getY()) return DirectionEnum.South;
		if(from.getY() > to.getY()) return DirectionEnum.North;
		return null;
	}
	
	/**
	 * Expresses difference in direction as an
	 * int from -2 to +1
	 * @param a
	 * @param b
	 * @return
	 */
	int directionDiff(DirectionEnum a, DirectionEnum b) {
		switch(a) {
		case North:
			switch(b) {
			case East: return  1;
			case North:return  0;
			case South:return -2;
			case West: return -1;
			}
		case East:
			switch(b) {
			case East: return  0;
			case North:return -1;
			case South:return  1;
			case West: return -1;
			}
		case South:
			switch(b) {
			case East: return -1;
			case North:return -2;
			case South:return  0;
			case West: return  1;
			}
		case West:
			switch(b) {
			case East: return -2;
			case North:return  1;
			case South:return -1;
			case West: return  0;
			}
		}
		
		// unreachable code, to make the stupid
		// eclipse compiler happy. >_<
		// This is a coding error and might cause
		// some complaints in an IDE different
		// from Eclipse, but since it's just
		// dead code it won't cause any troubles
		return 0;
	}
	
	/**
	 * Used as a heuristic for the distance between two points.
	 * Equals actual distance, if the path is completely clear.
	 * @param a
	 * @param b
	 * @return
	 */
	//private int manhattanDistance(GameGridNode a, Point b) {
	//	return manhattanDistance(a.pointHere, b);
	//}
	
	private int manhattanDistance(Point a, Point b) {
		return Math.abs(a.getX()-b.getX()) + Math.abs(a.getY()-b.getY());
	}
}
